package com.yj;

import edu.princeton.cs.algs4.StdOut;

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;

/**
 * Hello world!
 *
 */
public class App
{
    public static void main( String[] args )
    {
        System.out.println( "Hello World!" );
        System.out.println(gcd(1024, 1025));
        System.out.println((0+15)/2);
        System.out.println(2.0*Math.pow(Math.E, -6)*100000000.1);
        System.out.println(true && false || true && true);
        System.out.println((1+2.236)/2);
        System.out.println(1+2+3+4.0);
        System.out.println(1+2+"3");
        int a = Integer.parseInt(args[0]),b=Integer.parseInt(args[1]),c=Integer.parseInt(args[2]);
        System.out.printf("%d %d %d\n",a,b,c);
        if(a==b && b==c) {
            System.out.println("equal");
        } else {
            System.out.println("not equal");
        }
        double x = 0.5;
        double y = 0.4;
        System.out.println(x>=0&&x<=1);
        System.out.println(y>=0&&y<=1);
        int f=0;
        int g= 1;
        for (int i = 0; i <= 15; i++) {
            System.out.println(f);
            f =f +g;
            g=f-g;
        }

        double t = 256.0;
        double k = t;
        while (Math.abs(t - k/t) > .001)
            t = (k/t + t) / 2.0;
        StdOut.printf("%.5f\n", t);

        double num = 144.0;
        double temp = num;
        int iteCnt = 0;
        while(Math.abs(temp - num/temp)> .001 && iteCnt < 100) {
            temp = (temp+num/temp)/2;
            iteCnt++;
        }
        System.out.printf("%.5f\n",temp);

        double t1 = 3600.0;
        System.out.println(mysqrt((int)t1));

        int sum = 0;
        for (int i = 1; i < 11; i++)
            for (int j = 0; j < i; j++)
                sum++;
        StdOut.println(sum);

        sum = 0;
        for (int i = 1; i < 10; i *= 2)   // 1 2 4 8
            for (int j = 0; j < 10; j++)
                sum++;
        StdOut.println(sum);

        System.out.println('b');
        System.out.println('b' + 'c');
        System.out.println((char) ('a' + 4));
        System.out.println(Integer.toBinaryString(-20));
        System.out.println(Integer.toBinaryString(-20).length());
        System.out.println(toBinaryString(-20));
        boolean[][] bls = new boolean[10][10];
        for (int i = 0; i < bls.length; i++) {
            for (int j = 0; j < bls[i].length; j++) {
                if((int)(Math.random()+0.5)==1) {
                    bls[i][j] = true;
                }
            }
        }
        for (int i = 0; i < bls.length; i++) {
            if(i==0) {
                System.out.print(" ");
                for (int j = 0; j < bls[i].length; j++) {
                    System.out.print(" "+j);
                }
                System.out.println();
            }
            System.out.print(i);
            for (int j = 0; j < bls[i].length; j++) {
                System.out.printf(" %s", bls[i][j]?"*":" ");
            }
            System.out.println();

        }
        int[] aArr = new int[10];
        for (int i = 0; i < 10; i++)
            aArr[i] = 9 - i;
        for (int i = 0; i < 10; i++)
            aArr[i] = aArr[aArr[i]];
        for (int i = 0; i < 10; i++)
            System.out.print(i+" ");
        System.out.println();

        // 1.1.13 编写一段代码，打印出一个 M 行 N 列的二维数组的转置（交换行和列）。
        int[][] twoLayer = new int[10][5];
        for (int i = 0; i < twoLayer.length; i++) {
            for (int j = 0; j < twoLayer[i].length; j++) {
                twoLayer[i][j] = (int)(Math.random()+0.5);
            }
        }
        printTwoLayerArr(twoLayer);
        int[][] transforms = new int[5][10];
        for (int i = 0; i < twoLayer.length; i++) {
            for (int j = 0; j < twoLayer[i].length; j++) {
                transforms[j][i] = twoLayer[i][j];
            }
        }
        printTwoLayerArr(transforms);
        // 1.1.14 编写一个静态方法 lg()，接受一个整型参数 N，返回不大于 log2N 的最大整数。不要使用 Math 库。
        System.out.println(lg(8));
        // 1.1.15 编写一个静态方法 histogram()，接受一个整型数组 a[] 和一个整数 M 为参数并返回一个大小
        // 为M的数组，其中第i个元素的值为整数i在参数数组中出现的次数。如果a[]中的值均在0到M-1
        // 之间，返回数组中所有元素之和应该和 a.length 相等。
        int aArr1[] = new int[10];
        for (int i = 0; i < aArr1.length; i++) {
            aArr1[i] = (int)(Math.random()*10);
            System.out.printf("%d ", aArr1[i]);
        }
        System.out.println();
        System.out.println(Arrays.toString(histogram(aArr1, 8)));
        System.out.println(exR1(6));
        // mystery(2, 25) 和 mystery(3, 11) 的返回值是多少？给定正整数 a 和 b，mystery(a,b)
        //计算的结果是什么？将代码中的 + 替换为 * 并将 return 0 改为 return 1，然后回答相同
        //的问题。
        System.out.println(mystery(2,25));
        System.out.println(2*25);
        System.out.println(mystery(3,11));
        System.out.println(3*11);
        System.out.println(mystery1(2,25));
        System.out.println(Math.pow(2,25));
        System.out.println(mystery1(2,3));
        System.out.println(Math.pow(2,3));
        // 1.1.20 编写一个递归的静态方法计算 ln(N!) 的值。
        System.out.println(a_n(3));
        System.out.println(ln(a_n(3)));
        // 1.1.21 编写一段程序，从标准输入按行读取数据，其中每行都包含一个名字和两个整数。然后用
        //printf() 打印一张表格，每行的若干列数据包括名字、两个整数和第一个整数除以第二个整数
        //的结果，精确到小数点后三位。可以用这种程序将棒球球手的击球命中率或者学生的考试分数
        //制成表格
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[][] arr = new int[n][2];
//        String[] names = new String[n];
//        for (int i = 0; i < n; i++) {
//            String name = sc.next();
//            int score = sc.nextInt();
//            int total = sc.nextInt();
//            names[i] = name;
//            arr[i][0] = score;
//            arr[i][1] = total;
//        }
//        sc.close();
//        System.out.printf("姓名 分数 总分 命中率\n");
//        for (int i = 0; i < n; i++) {
//            System.out.printf("%-3s %-3d %-3d %-3.3f\n", names[i], arr[i][0],arr[i][1],arr[i][0]*1d/arr[i][1]);
//        }
        // 1.1.22 使用 1.1.6.4 节中的 rank() 递归方法重新实现 BinarySearch 并跟踪该方法的调用。每当该方法
        //被调用时，打印出它的参数 lo 和 hi 并按照递归的深度缩进。提示：为递归方法添加一个参数
        //来保存递归的深度。

        // 1.1.27 二项分布。估计用以下代码计算 binomial(100, 50) 将会产生的递归调用次数：
        //public static double binomial(int N, int k, double p)
        //{
        //if (N == 0 && k == 0) return 1.0; and if (N < 0 || k < 0) return 0.0;
        //return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1);
        //}
        //将已经计算过的值保存在数组中并给出一个更好的实现。
        System.out.println(binomialWithArray(10, 5, 0.5));
        // 1.1.28 删除重复元素。修改 BinarySearch 类中的测试用例来删去排序之后白名单中的所有重复元素。
        Integer[] whiteList = new Integer[]{1,1,2,2,3,4,6,6,6,6,7,6,7,6,7,8,9,5,5,5};
        // whiteList = delDuplicateElement(whiteList);
        System.out.println(Arrays.toString(whiteList));
        // 1.1.29 等值键。为 BinarySearch 类添加一个静态方法 rank()，它接受一个键和一个整型有序数组（可
        //能存在重复键）作为参数并返回数组中小于该键的元素数量，以及一个类似的方法 count() 来
        //返回数组中等于该键的元素的数量。注意：如果 i 和 j 分别是 rank(key,a) 和 count(key,a)
        //的返回值，那么 a[i..i+j-1] 就是数组中所有和 key 相等的元素。
        Arrays.sort(whiteList);
        System.out.println(Arrays.toString(whiteList));
        int key = 7;
        System.out.println(rank(whiteList, key));
        System.out.println(count(whiteList, key));
        // 1.1.30 数组练习。编写一段程序，创建一个 N×N 的布尔数组 a[][]。其中当 i 和 j 互质时（没有相同
        //因子），a[i][j] 为 true，否则为 false。
        boolean[][] aa = new boolean[10][10];
        for (int i = 0; i < aa.length; i++) {
            for (int j = 0; j < aa[i].length; j++) {
                if(isHuZhi(i,j)) {
                    aa[i][j] = true;
                }
            }
        }
        printTwoLayerArrBl(aa);
    }

    static class MainFrame extends JFrame {
        private MyPanel myPanel;
        public MainFrame() throws HeadlessException {
            this.setSize(400, 500);
            myPanel = new MyPanel(this.getWidth(),this.getHeight(), 300, 300);
            this.add(myPanel);
            Dimension screensize = Toolkit.getDefaultToolkit().getScreenSize();
            int x = (int) screensize.getWidth() / 2 - this.getWidth() / 2;
            int y = (int) screensize.getHeight() / 2 - this.getHeight() / 2;
            this.setLocation(x, y);
            this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            this.setVisible(true);
        }
//        1.1.31 随机连接。编写一段程序，从命令行接受一个整数 N 和 double 值 p（0 到 1 之间）作为参数，
//        在一个圆上画出大小为 0.05 且间距相等的 N 个点，然后将每对点按照概率 p 用灰线连接。
        public static void main(String[] args) {
            MainFrame mainFrame = new MainFrame();
            while(true) {
                mainFrame.myPanel.circleWidth--;
                mainFrame.myPanel.circleHeight--;
                mainFrame.myPanel.repaint();
                try {
                    Thread.sleep(300);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
            }
        }

    }


    // 定义一个MyPanel面板，用于绘图区域
    static class MyPanel extends JPanel {
        private int windowWidth;
        private int windowHeight;
        private int circleWidth;
        private int circleHeight;

        public MyPanel(int windowWidth, int windowHeight, int circleWidth, int circleHeight) {
            this.windowWidth = windowWidth;
            this.windowHeight = windowHeight;
            this.circleWidth = circleWidth;
            this.circleHeight = circleHeight;
        }

        //覆盖JPanel
        // Graphics 是绘图的重要类，可以理解成一支画笔
        public void paint(Graphics g) {
            // 	1. 调用父类函数完成初始化任务
            //	这句话不可以少
            super.paint(g);
            Graphics2D g2d = (Graphics2D) g;
            // 让线段平滑
            g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
            g2d.setRenderingHint(RenderingHints.KEY_STROKE_CONTROL, RenderingHints.VALUE_STROKE_DEFAULT);
            Stroke stroke = new BasicStroke(10,BasicStroke.CAP_ROUND,BasicStroke.JOIN_ROUND);
            g2d.setStroke(stroke);
            // 先画出一个圆圈
            int x =  (int) windowWidth / 2 - circleWidth / 2;
            int y =  (int) windowHeight / 2 - circleHeight / 2;
            g.drawOval(x, y, circleWidth, circleHeight);
        }
    }

    public static boolean isHuZhi(int a, int b) {
        if(a==1 || b==1) {
            return true;
        }
        if(a==0 && b==1) {
            return true;
        }
        if(a==1 && b==0) {
            return true;
        }
        int t =gcd(a, b);
        if(t==1) return true;
        else return false;
    }

    public static int rank(Integer[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if(key<=arr[i]) {
                return i;
            }
        }
        return 0;
    }

    public static int count(Integer[] arr, int key) {
        int cnt=0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==key) {
                cnt++;
            }
            if(key < arr[i]) {
                break;
            }
        }
        return cnt;
    }

    public static Integer[] delDuplicateElement(Integer[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int x = arr[i];
            Integer ans = binarySearch(arr, i+1,len-1, x);
            while(ans>-1) {
                len = delElement(arr, len, ans);
                ans = binarySearch(arr, i+1,len-1, x);
            }
        }
        Integer[] newArr = new Integer[len];
        for (int i = 0; i < len; i++) {
            newArr[i] = arr[i];
        }
        return newArr;
    }

    public static int delElement(Integer[] arr, int len, int index) {
        for (int i = index; i < len-1; i++) {
            arr[i] = arr[i+1];
        }
        len--;
        return len;
    }

    public static Integer binarySearch(Integer[] arr, int l,int r, Integer x) {
        if(l>r) return -1;
        Integer ans = -1;
        while(l<=r) {
            int mid = (l+r)/2;
            if(x>arr[mid]) {
                l = mid+1;
            } else if(x<arr[mid]) {
                r = mid-1;
            } else {
                ans = mid;
                return ans;
            }
        }
        return ans;
    }

    public static double binomialWithArray(int N,int k,double p){
        double[][] binomialArrays = new double[N+1][k+1];

        binomialArrays[0][0] = 1.0;
        for (int i=1; i<=N; i++){
            binomialArrays[i][0] = (1-p)*binomialArrays[i-1][0];
        }

        for (int i=1; i<=N; i++){
            for (int j=1; j<=k; j++){
                binomialArrays[i][j] = (1-p)*binomialArrays[i-1][j] + p*binomialArrays[i-1][j-1];
            }
        }
        return binomialArrays[N][k];

    }

    public static double binomial(int N, int k, double p)
    {
    if (N == 0 && k == 0) return 1.0;
    if (N < 0 || k < 0) return 0.0;
    return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1, p);
    }

    public static int a_n(int n) {
        if(n==0) return 1;
        return n*a_n(n-1);
    }

    static class Fibonacci
    {
        static long f[] = new long[10000];
        static {
            f[0] = 0;
            f[1] = 1;
        }
        // 计算机用这段程序在一个小时之内能够得到 F(N) 结果的最大 N 值是多少？开发 F(N) 的一
        // 个更好的实现，用数组保存已经计算过的值。
        public static long F(int N)
        {
            if(N == 0) return f[0];
            if(N == 1) return f[1];
            f[N] = f[N-1] + f[N-2];
            return f[N];
        }
        public static void main(String[] args)
        {
            for (int N = 0; N < 100; N++)
                StdOut.println(N + " " + F(N));
        }
    }

    public static int mystery(int a, int b)
    {
        if (b == 0) return 0;
        if (b % 2 == 0) return mystery(a+a, b/2);
        return mystery(a+a, b/2) + a;
    }

    public static double mystery1(double a, int b)
    {
        if (b == 0) return 1;
        if (b % 2 == 0) return mystery1(a*a, b/2);
        return mystery1(a*a, b/2) * a;
    }

    public static String exR1(int n)
    {
        if (n <= 0) return "";
        return exR1(n-3) + n + exR1(n-2) + n;
    }

    public static int[] histogram(int[] a, int m) {
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            cntMap.merge(a[i], 1, (old, news) -> old+news);
        }
        int ans[] = new int[m];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = cntMap.getOrDefault(i, 0);
        }
        return ans;
    }

    public static int lg(int n) {
        int x = -1;
        int res = 1;
        while(res<n) {
            x++;
            res = 1;
            for (int i = 0; i < x; i++) {
                res*=2;
            }
        }
        if(res > n) {
            x = x-1;
        }
        return x;
    }

    public static int ln(int n) {
        int x = -1;
        double res = 1;
        while(res<n) {
            x++;
            res = mystery1(Math.E, x);
        }
        if(res>n) {
            x--;
        }
        return x;
    }

    public static void printTwoLayerArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.printf("%d ", arr[i][j]);
            }
            System.out.println();
        }
    }

    public static void printTwoLayerArrBl(boolean[][] arr) {
        for (int i = 0; i < 1; i++) {
            System.out.print("  ");
            for (int j = 0; j < arr[i].length; j++) {
                System.out.printf("%-5d ",j);
            }
            System.out.println();
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%-2d",i);
            for (int j = 0; j < arr[i].length; j++) {
                System.out.printf("%-5s ", arr[i][j]);
            }
            System.out.println();
        }
    }

    public static String toBinaryString(int n) {
        int x = 0x80000000;
        if(n<0) {
            // n = n & x;
            StringBuilder stringBuilder = new StringBuilder();
            while((n & x) == x && n<-1) {
                stringBuilder.insert(0, n & 1);
                n = n>>1;
            }
            while(stringBuilder.length()<32) {
                stringBuilder.insert(0,1);
            }
            return stringBuilder.toString();
        }
        if(n==0) {
            return "0";
        }
        StringBuilder stringBuilder = new StringBuilder();
        while(n > 0) {
            stringBuilder.insert(0,n%2);
            n = n/2;
        }
        return stringBuilder.toString();
    }

    public static int mysqrt(int x) {
        if(x<=0) {
            return 0;
        }
        int left = 1,right =x;
        while(left<=right) {
            int mid = (left + right) /2;
            if(mid<=x/mid && (mid+1)>x/(mid+1)) {
                return mid;
            } else if(mid < x/mid) {
                left = mid+1;
            } else {
                right = mid -1;
            }
        }
        return -1;
    }

    public static int gcd(int p, int q) {
        if(q==0) return p;
        int r = p % q;
        return gcd(q, r);
    }

    static class Main {
        public static void rank(int[] a, String[] keys, char arg){
            int[] whiteList = new int[]{7,1,1,1,2,2,4,2,4,6,5,3,3,3};
            Arrays.sort(whiteList);
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < whiteList.length-1; i ++){
                if(whiteList[i] != whiteList[i+1]){
                    list.add(whiteList[i]);
                }
            }
            if(whiteList.length>1 && whiteList[whiteList.length-1]!=whiteList[whiteList.length-2]) {
                list.add(whiteList[whiteList.length-1]);
            }

            Iterator<Integer> iterator= list.iterator();
            while (iterator.hasNext()){
                System.out.println(iterator.next());
            }
        }
        public static void main(String[] args) {
            rank(null, null, 'a');
        }
    }
}
